#include "CrossRiver.h"
#include <stack>

#define CROSS_COMBIN_NUM 5
cross ways[CROSS_COMBIN_NUM] = { {BoatSideLeft, 2, 0}, {BoatSideLeft, 0, 1}, {BoatSideLeft, 0, 2}, {BoatSideLeft, 1, 0}, {BoatSideLeft, 1, 1} };

void CrossRiver::Init()
{
	begin.Init();
	memo.insert(begin.GetKey());
}

void CrossRiver::Do()
{
	//_Dfs(begin);
	_Bfs();
}

void CrossRiver::_Dfs(status s)
{
	if (s.IsDone())
	{
		ShowCrossPath();
		return;
	}

	for (int i = 0; i < CROSS_COMBIN_NUM; i++)
	{
		cross way = ways[i];
		way.side = s.side;
		if (!s.CanCross(way))
		{
			continue;
		}

		status tmp = s;
		tmp.Cross(way);
		if (memo.find(tmp.GetKey()) != memo.end())
		{
			continue;
		}
		memo.insert(tmp.GetKey());
		crossPath.push_back(way);
		_Dfs(tmp);
		crossPath.pop_back();
	}
}

void CrossRiver::_Bfs()
{
	std::set<int> setNode;
	std::deque<statusNode*> q;

	statusNode* node = new statusNode{ nullptr, begin };
	q.push_back(node);

	while (!q.empty())
	{
		statusNode* node = q.front();
		q.pop_front();
		if (node->s.IsDone())
		{
			ShowStatusLinkPath(node);
			continue;
		}
		for (int i = 0; i < CROSS_COMBIN_NUM; i++)
		{
			cross way = ways[i];
			way.side = node->s.side;
			
			if (!node->s.CanCross(way))
			{
				continue;
			}

			status tmp = node->s;
			tmp.Cross(way);

			if (setNode.find(tmp.GetKey()) != setNode.end())
			{
				continue;
			}
			setNode.insert(tmp.GetKey());

			q.push_back(new statusNode{ node, tmp });
		}
	}
}

void CrossRiver::ShowCrossPath()
{
	status s = begin;
	printf("path size %d list:\n", crossPath.size());
	for (const auto& u : crossPath)
	{
		if (u.side == BoatSideLeft)
		{
			printf("monster %d player %d ->\n", u.monsterCount, u.playerCount);
		}
		else
		{
			printf("<- monster %d player %d\n", u.monsterCount, u.playerCount);
		}
		s.Cross(u);
		s.Show();
	}
	printf("\n");
}

void CrossRiver::ShowStatusLinkPath(statusNode* node)
{
	std::stack<status> result;
	while (node)
	{
		result.push(node->s);
		node = node->parent;
	}
	printf("status path size %d list:\n", result.size());
	while (!result.empty())
	{
		status s = result.top();
		result.pop();
		s.Show();
	}
	printf("\n");
}
